package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.WC;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author tzp
 * @since 2020/9/27
 */
public class WC208_4 implements WC {
    int[][] requests;

    public int maximumRequests(int n, int[][] requests) {
        this.requests = requests;
        HashMap<Integer, ArrayList<Integer>> rqs = new HashMap<>();
        for (int[] request : requests) {
            rqs.compute(request[0], (integer, old) -> {
                if (old == null) {
                    old = new ArrayList<>();
                }
                old.add(integer);
                return old;
            });
        }

        ArrayList<Integer> from = new ArrayList<>();
        ArrayList<Integer> to = new ArrayList<>();
        return maxRec(0, from, to);
    }

    public int maxRec(int index, ArrayList<Integer> from, ArrayList<Integer> to) {
        ArrayList<Integer> newFrom = new ArrayList<>(from);
        ArrayList<Integer> newTo = new ArrayList<>(to);
        int max = 0;

        //不包含当前
        if (index == requests.length - 1) {
            max = 0;
        } else {
            max = Math.max(max, maxRec(index + 1, newFrom, newTo));
        }

        //包含当前
        if (!newFrom.remove(new Integer(requests[index][1]))) {
            newTo.add(new Integer(requests[index][1]));
        }
        if (!newTo.remove(new Integer(requests[index][0]))) {
            newFrom.add(new Integer(requests[index][0]));
        }
        int currentFit = newFrom.size() == 0 && newTo.size() == 0 ? 1 : 0;
        if (index == requests.length - 1) {
            max = Math.max(max, currentFit);
        } else {
            int sub = maxRec(index + 1, newFrom, newTo);
            if (sub > 0) {
                max = Math.max(max, sub + 1);
            } else {
                max = Math.max(max, currentFit);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] a = {{0, 3}, {3, 1}, {1, 2}, {2, 0}};
//        int[][] a = {{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}};
//        int[][] a = {{1, 2}, {1, 2}, {2, 2}, {0, 2}, {2, 1}, {1, 1}, {1, 2}};
//        int[][] a = {{1, 2}, {2, 1}, {2, 3}, {2, 4}, {3, 1}};
        System.out.println(new WC208_4().maximumRequests(100, a));
    }
}
